package com.gxc.array;

/**
 * 已知一棵二叉树中没有重复节点，并且给定了这棵树的中序遍历数组和先序遍历数组，返回后序遍历数组。
 * 比如给定:
 * int[] pre =( 1,2,4,5,3,6,7)
 * int[] in = { 4,2,5,1,6,3,7 )
 * 返回:(4,5,2,6,7,3,1)
 *
 * 解法：
 * 先序遍历:头左右
 * 中序遍历:左头右
 * 后序遍历:左右头
 *
 * 根据头节点在中序遍历的位置，分为左子节点和右子节点，然后递归遍历左子节点和右子节点
 */
public class Ergodic {

    public static void main(String[] args) {
        int[] pre = new int[]{1,2,4,5,3,6,7};
        int[] in = new int[]{4,2,5,1,6,3,7};

        int length = pre.length;
        int[] arr = new int[length];
        set(pre, in, arr, 0, length-1, 0, length-1, 0, length-1);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

        System.out.println("----");
        int[] arr2 = new int[length];
        set(pre, in, arr2, 0, length-1, 0, length-1, 0, length-1);

        for (int i = 0; i < arr2.length; i++) {
            System.out.print(arr2[i] + " ");
        }
    }

    private static void set(int[] pre, int[] in, int[] arr,
                               int preS, int preE,
                               int inS, int inE,
                               int posS, int posE) {

        arr[posE] = pre[preS];
        if (posE == posS) {
            return;
        }
        int headPos = headPos(in, pre[preS]);
        int length = headPos-inS;
        set(pre, in, arr, preS+1, preS+1+length-1, inS, inS+length-1, posS, posS+length-1);
        set(pre, in, arr, preS+1+length, preE, headPos+1, inE, posS+length, posE-1);
    }

    private static void set2(int[] pre, int[] in, int[] arr,
                            int preS, int preE,
                            int inS, int inE,
                            int posS, int posE) {
        //不会发生 preS+1>preS+1+length-1  length==0
        if (preS>preE) return;

        if (preS == preE) {
            arr[posS] = pre[preS];
            return;
        }
        arr[posE] = pre[preS];

        int headPos = headPos(in, pre[preS]);
        int length = headPos-inS;
        set2(pre, in, arr, preS+1, preS+1+length-1, inS, inS+length-1, posS, posS+length-1);
        set2(pre, in, arr, preS+1+length, preE, headPos+1, inE, posS+length, posE-1);
    }

    /**
     *
     * @param in
     * @param j
     * @return
     */
    private static int headPos(int[] in, int j) {
        for (int i = 0; i < in.length; i++) {
            if (j == in[i]) return i;
        }
        return 0;
    }
}
